GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Syntaxbaum</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Syntaxbaum</span></h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p>Ein <b>Syntax-</b>, <b>Ableitungs-</b> oder <b>Parsebaum</b> ist ein Begriff aus der <a href="Theoretische_Informatik" title="Theoretische Informatik">theoretischen Informatik</a> und der <a href="Linguistik" class="mw-redirect" title="Linguistik">Linguistik</a>. Er bezeichnet eine hierarchische Darstellung der Zergliederung eines Textes. Syntaxbäume werden sowohl als Hilfsmittel zur graphischen Visualisierung der Zerlegung eingesetzt als auch, in Form einer <a href="Datenstruktur" title="Datenstruktur">Datenstruktur</a>, zur Darstellung dieser Zergliederung für die maschinelle Weiterverarbeitung z. B. in einem <a href="Compiler" title="Compiler">Compiler</a> oder <a href="Maschinelle_%C3%9Cbersetzung" title="Maschinelle Übersetzung">Übersetzer</a>.

</p><p>Die verschiedenen Bezeichnungen werden in der Literatur nicht einheitlich verwendet. Formal präzise definiert ist nur der Terminus <i>Ableitungsbaum</i>, der sich auf den Begriff der <a href="Ableitung_(Informatik)" title="Ableitung (Informatik)">Ableitung</a> stützt. Andere Bezeichnungen für verschiedenartige Bäume können dann, wie unten beschrieben, bei Bedarf technisch näher definiert werden.

</p><p>Anders als in der Informatik, in der Sprachen auch den technischen Möglichkeiten folgend definiert werden können, findet die Linguistik bei der Behandlung <a href="Nat%C3%BCrliche_Sprache" title="Natürliche Sprache">natürlicher Sprachen</a> schwierigere Voraussetzungen vor, vor allem weil die Reihenfolge der Bestandteile in einem Satz variieren kann.

</p>

<div class="mw-heading mw-heading2"><h2 id="Einleitung">Einleitung</h2></div>

<p>Bei der (mechanischen) Analyse von <a href="Nat%C3%BCrliche_Sprache" title="Natürliche Sprache">natürlichsprachlichen</a> Sätzen oder <a href="Formale_Sprache" title="Formale Sprache">formalen</a> Texten (z. B. Computerprogrammen) findet direkt nach der <a href="Lexikalische_Analyse" title="Lexikalische Analyse">lexikalischen Analyse</a> (der Zergliederung in <a href="Token_(%C3%9Cbersetzerbau)" title="Token (Übersetzerbau)">Token</a> oder <a href="Symbol_(Informatik)" title="Symbol (Informatik)">Symbole</a>) oft eine hierarchische Zusammenfassung der Symbole zu zusammenhängenden Satzteilen (<a href="Konstituente" title="Konstituente">Konstituenten</a>) bzw. Teilabschnitten des formalen Textes statt. Umgekehrt kann dies wiederum auch als eine Zergliederung des Textes aufgefasst werden. Im Ergebnis erhält man einen <a href="Baum_(Datenstruktur)" title="Baum (Datenstruktur)">Baum</a>, wie den rechts gezeigten. Neben der zeichnerischen Form werden auch geklammerte Darstellungen für Syntaxbäume verwendet: <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [_{S}\ [_{\mathit {NP}}\ John]\ [_{\mathit {VP}}\ [_{V}\ hit]\ [_{\mathit {NP}}\ [_{\mathit {Det}}\ the]\ [_{N}\ ball]]]].}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [_{S}\ [_{\mathit {NP}}\ John]\ [_{\mathit {VP}}\ [_{V}\ hit]\ [_{\mathit {NP}}\ [_{\mathit {Det}}\ the]\ [_{N}\ ball]]]].}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f2839a63dd19e79ecaf8cc3f2c51790d2367cafc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:45.657ex; height:2.843ex;" alt="{\displaystyle [_{S}\ [_{\mathit {NP}}\ John]\ [_{\mathit {VP}}\ [_{V}\ hit]\ [_{\mathit {NP}}\ [_{\mathit {Det}}\ the]\ [_{N}\ ball]]]].}" loading="lazy"></span>

</p><p>Technisch bezeichnet man den nebenstehenden Baum auch als <i>konkreten Ableitungsbaum</i>, da er die resultierende Struktur anhand des konkreten Textes exakt darstellt. In der Linguistik sind jedoch auch Modelle gängig, die mehrere Schichten der Repräsentation vorsehen (z. B. Oberflächen- und <a href="Tiefenstruktur" title="Tiefenstruktur">Tiefenstruktur</a>).

</p><p>Oftmals werden die Knoten des Baums mit Attributen angereichert (in der Linguistik sind dies dann vor allem <a href="Grammatische_Kategorie" title="Grammatische Kategorie">morphologische Kategorien</a>).<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> Man erhält so einen <i>attributierten Syntaxbaum</i> mit zugehöriger <a href="Attributgrammatik" title="Attributgrammatik">attributierter Grammatik</a>. Während in den ersten beiden Baumdarstellungen eine <a href="Kontextfreie_Grammatik" title="Kontextfreie Grammatik">kontextfreie Grammatik</a> verwendet wird, kommt in letzterer die <a href="Kontextabh%C3%A4ngigkeit" class="mw-redirect" title="Kontextabhängigkeit">Kontextabhängigkeit</a> zum Tragen. Diese Unterschiede spiegeln sich in der <a href="Chomsky-Hierarchie" title="Chomsky-Hierarchie">Chomsky-Hierarchie</a> wider. Im Compilerbau spricht man in solchen Fällen bereits von <a href="Compiler#Semantische_Analyse" title="Compiler">semantischer Analyse</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Ableitungsbäume"><span id="Ableitungsb.C3.A4ume"></span>Ableitungsbäume</h2></div>

<p>Man betrachte eine <a href="Kontextfreie_Grammatik" title="Kontextfreie Grammatik">kontextfreie Grammatik</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G=\left(N,\Sigma ,P,S\right)}">

<mrow>

<mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G=\left(N,\Sigma ,P,S\right)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9159da9e27b1afb873224c1d8984d6c80e651357.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.823ex; height:2.843ex;" alt="{\displaystyle G=\left(N,\Sigma ,P,S\right)}" loading="lazy"></span>.

Ein Ableitungsbaum dazu ist ein <a href="Baum_(Datenstruktur)" title="Baum (Datenstruktur)">Baum</a>, dessen Knoten mit Symbolen aus <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma \cup N\cup \{\varepsilon \}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma \cup N\cup \{\varepsilon \}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c1111483dba5c5a6090902365bd79d58fe0898c5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.315ex; height:2.843ex;" alt="{\displaystyle \Sigma \cup N\cup \{\varepsilon \}}" loading="lazy"></span> (also <a href="Terminalsymbol" title="Terminalsymbol">Terminal-</a> und Nichtterminalsymbolen und dem <a href="Leeres_Wort" title="Leeres Wort">leeren Wort</a>) beschriftet sind. Der Baum ist <i>geordnet</i>, d. h. die Kinder jedes Knotens haben eine feste Reihenfolge, und für die Beschriftung gilt:

</p>

<ul><li>Die <a href="Wurzel_(Graphentheorie)" title="Wurzel (Graphentheorie)">Wurzel</a> ist mit dem Startsymbol <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"></span> beschriftet. <i>Diese Eigenschaft wird gelegentlich nicht verlangt. Ein Baum, der sie erfüllt, wird als </i>vollständiger<i> Ableitungsbaum bezeichnet.</i></li>

<li>Wenn die Kinder eines mit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span> beschrifteten inneren Knotens mit den Symbolen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z_{1},\ldots ,z_{m}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z_{1},\ldots ,z_{m}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/83b1fff458f1d7896392fd380cf6360a774734db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.07ex; height:2.009ex;" alt="{\displaystyle z_{1},\ldots ,z_{m}}" loading="lazy"></span> (in dieser Reihenfolge) beschriftet sind, muss die Grammatik die Regel <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\to z_{1}\ldots z_{m}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\to z_{1}\ldots z_{m}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/625bad0dc042d1c44eadf75c28c8f3a0856e23b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.746ex; height:2.509ex;" alt="{\displaystyle A\to z_{1}\ldots z_{m}}" loading="lazy"></span> enthalten.</li>

<li>Die <a href="Blatt_(Graphentheorie)" class="mw-redirect" title="Blatt (Graphentheorie)">Blätter</a> des Baumes sind mit Symbolen aus <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma \cup \{\varepsilon \}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma \cup \{\varepsilon \}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/08ff0af973b4e628344c0f78bb82e9ec45a22333.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.669ex; height:2.843ex;" alt="{\displaystyle \Sigma \cup \{\varepsilon \}}" loading="lazy"></span> beschriftet.</li>

<li>Ist ein Blatt mit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varepsilon }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon }</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a30c89172e5b88edbd45d3e2772c7f5e562e5173.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.083ex; height:1.676ex;" alt="{\displaystyle \varepsilon }" loading="lazy"></span> gekennzeichnet, so ist es der einzige Nachfolger seines Vorgängerknotens.</li></ul>

<p>Als innere Knoten kommen also nur Nichtterminalsymbole in Frage sowie für die Blätter nur die Terminalsymbole oder das leere Wort.

</p>

<div class="mw-heading mw-heading3"><h3 id="Konstruktion_von_Ableitungsbäumen"><span id="Konstruktion_von_Ableitungsb.C3.A4umen"></span>Konstruktion von Ableitungsbäumen</h3></div>

<p>Mögliche Syntaxbäume/diagramme lassen sich für kurze Texte oft leicht durch Befolgen der Produktionsregeln erstellen.

Für längere Texte stehen viele <a href="Parser" title="Parser">mechanische Verfahren</a> zur Verfügung.

</p><p>Beispielsweise liegen dem einleitend gezeigten Syntaxdiagramm u. a. folgende Regeln zugrunde:

</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{array}{lll}S&\rightarrow &NP\ VP\\NP&\rightarrow &{\mathtt {John}}\\NP&\rightarrow &Det\ N\\VP&\rightarrow &V\ NP\\\end{array}}\quad \quad {\begin{array}{lll}V&\rightarrow &{\mathtt {hit}}\\Det&\rightarrow &{\mathtt {the}}\\N&\rightarrow &{\mathtt {ball}}\end{array}}}">

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{array}{lll}S&\rightarrow &NP\ VP\\NP&\rightarrow &{\mathtt {John}}\\NP&\rightarrow &Det\ N\\VP&\rightarrow &V\ NP\\\end{array}}\quad \quad {\begin{array}{lll}V&\rightarrow &{\mathtt {hit}}\\Det&\rightarrow &{\mathtt {the}}\\N&\rightarrow &{\mathtt {ball}}\end{array}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8a534e1a94dfe159ce884216267564f06664b103.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.671ex; width:40.547ex; height:12.509ex;" alt="{\displaystyle {\begin{array}{lll}S&\rightarrow &NP\ VP\\NP&\rightarrow &{\mathtt {John}}\\NP&\rightarrow &Det\ N\\VP&\rightarrow &V\ NP\\\end{array}}\quad \quad {\begin{array}{lll}V&\rightarrow &{\mathtt {hit}}\\Det&\rightarrow &{\mathtt {the}}\\N&\rightarrow &{\mathtt {ball}}\end{array}}}" loading="lazy"></span>

</p><p>Um nun einen Ableitungbaum zu erzeugen, kann man die Regeln schrittweise von der Wurzel aus anwenden, indem

man systematisch je ein Nonterminal der linken Seite der Regel durch die Symbole auf der rechten Seite ersetzt,

bis nur noch Terminale übrig sind:

</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S\ \Rightarrow \ NP\ VP\ \Rightarrow \ {\mathtt {John}}\ VP\ \Rightarrow \ {\mathtt {John}}\ V\ NP\ \Rightarrow \ {\mathtt {John\ hit}}\ NP\ \Rightarrow \ {\mathtt {John\ hit}}\ Det\ N\Rightarrow \ {\mathtt {John\ hit\ the}}\ N\Rightarrow \ {\mathtt {John\ hit\ the\ ball}}}">

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S\ \Rightarrow \ NP\ VP\ \Rightarrow \ {\mathtt {John}}\ VP\ \Rightarrow \ {\mathtt {John}}\ V\ NP\ \Rightarrow \ {\mathtt {John\ hit}}\ NP\ \Rightarrow \ {\mathtt {John\ hit}}\ Det\ N\Rightarrow \ {\mathtt {John\ hit\ the}}\ N\Rightarrow \ {\mathtt {John\ hit\ the\ ball}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/edf5c5aa09e4c88e589cb9991307582b0cb607d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:131.344ex; height:2.176ex;" alt="{\displaystyle S\ \Rightarrow \ NP\ VP\ \Rightarrow \ {\mathtt {John}}\ VP\ \Rightarrow \ {\mathtt {John}}\ V\ NP\ \Rightarrow \ {\mathtt {John\ hit}}\ NP\ \Rightarrow \ {\mathtt {John\ hit}}\ Det\ N\Rightarrow \ {\mathtt {John\ hit\ the}}\ N\Rightarrow \ {\mathtt {John\ hit\ the\ ball}}}" loading="lazy"></span>

</p><p>Bei jedem der Schritte zeichnet man dabei von oben nach unten ein Stück des Syntaxbaums. Man kann die Regeln aber auch umgekehrt anwenden und mit dem niedergeschriebenen Satz beginnen und darüber den

Baum schrittweise von unten nach oben aufbauen.

</p>

<div class="mw-heading mw-heading3"><h3 id="Ableitungsbäume_bei_ein-_und_mehrdeutigen_Grammatiken"><span id="Ableitungsb.C3.A4ume_bei_ein-_und_mehrdeutigen_Grammatiken"></span>Ableitungsbäume bei ein- und mehrdeutigen Grammatiken</h3></div>

<p>Falls es für ein Wort der Sprache einer Grammatik mehr als einen Ableitungsbaum gibt, spricht man von einer <a href="Mehrdeutige_Grammatik" title="Mehrdeutige Grammatik">mehrdeutigen Grammatik</a>, sonst von einer eindeutigen.

Beispielsweise ist die folgende Grammatik mehrdeutig

</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{array}{lll}S&\rightarrow &S\ S\\S&\rightarrow &a\end{array}}}">

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{array}{lll}S&\rightarrow &S\ S\\S&\rightarrow &a\end{array}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/68ff319e39a67b1d551c107edd523f72aca8b1ef.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:12.799ex; height:6.176ex;" alt="{\displaystyle {\begin{array}{lll}S&\rightarrow &S\ S\\S&\rightarrow &a\end{array}}}" loading="lazy"></span>

</p><p>da man etwa "a a a" in zwei verschiedenen Weisen einteilen kann: "[a a] a" und "a [a a]". Nur eine mögliche Einteilung erlaubt hingegen folgende Grammatik

</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{array}{lll}S&\rightarrow &a\ S\\S&\rightarrow &a\end{array}}}">

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{array}{lll}S&\rightarrow &a\ S\\S&\rightarrow &a\end{array}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/677b434e30deb1d55772262e284af025a69d86ce.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:12.529ex; height:6.176ex;" alt="{\displaystyle {\begin{array}{lll}S&\rightarrow &a\ S\\S&\rightarrow &a\end{array}}}" loading="lazy"></span>

</p><p>Bei mehrdeutigen Grammatiken kann die Zahl möglicher Ableitungsbäume für ein und dasselbe Wort mit der Länge des Wortes stark ansteigen. In diesem Fall sind Ableitungsbäume keine geeignete Darstellung für die Gesamtheit möglicher Ableitungen mehr. Bei formalen Sprachen wird die konkrete (Oberflächen-)Grammatik meist eindeutig formuliert. Abstrakte Grammatiken sind dagegen oft mehrdeutig, wobei sich die Eindeutigkeit des abstrakten Ableitungsbaums dann durch den Gang der Analyse aus dem konkreten ergibt.

</p>

<div class="mw-heading mw-heading2"><h2 id="Abstrakte_Syntaxbäume"><span id="Abstrakte_Syntaxb.C3.A4ume"></span>Abstrakte Syntaxbäume</h2></div>

<p>Für die Darstellung von Syntaxbäumen als <a href="Datenstruktur" title="Datenstruktur">Datenstruktur</a> in einem Rechner wird die Bezeichnung <i>abstrakter Syntaxbaum</i> (engl.: abstract syntax tree (AST)) inzwischen recht einheitlich verwendet, wobei die Terminologie auch hier schwankt und z. B. ebenfalls von <i>abstrakten Ableitungsbäumen</i>, <i>Operatorbäumen</i> o. Ä. die Rede sein kann. Ein exakter Zusammenhang von abstraktem Syntaxbaum und konkretem Ableitungsbaum wird in der Literatur z. T. angedeutet. Allerdings gehen bei diesen neben einer Vergröberung des Ableitungsbaums auch Erfordernisse der weiteren Verarbeitung mit in den Aufbau ein, so dass eine direkte formale Herleitung aus der Oberflächengrammatik meist im Ergebnis nicht zufriedenstellend ist.

</p><p>Der kontextfreien Oberflächengrammatik steht dann eine <i>abstrakte Grammatik</i> gegenüber, die im engeren Sinne aber meist ein <a href="Funktionallogische_Programmierung#Algebraische_Datentypen" title="Funktionallogische Programmierung">algebraischer Datentyp</a> ist. Die Syntaxbäume werden dann als <a href="Sortenlogik#Terme_in_vielsortiger_Logik" title="Sortenlogik">vielsortige Terme</a> technisch repräsentiert. Die Analyse befindet sich dabei im Übergang zwischen grammatischen und algebraisch-logischen Begriffen, so dass hier fließend sowohl von Nonterminalen und Typen oder von Bäumen und Termen die Rede sein kann.

</p>

<div class="mw-heading mw-heading3"><h3 id="Beispiel">Beispiel</h3></div>

<p>Die nebenstehende Abbildung zeigt konkrete und abstrakte Syntaxbäume für die nachfolgenden Grammatiken.

</p>

<th>konkrete Grammatik

</th>

<th>abstrakte Grammatik

</th>

<th>algebraischer Typ

</th></tr>

<tr>

<td><pre class="rahmenfarbe4">E :: E "+" T -- Ausdruck

 :: T

T :: T "*" F -- Term

 :: F

F :: V -- Faktor

 :: N

 :: "(" E ")"

V -- Variable

N -- Zahl

</pre>

</td>

<td><pre class="rahmenfarbe4">E :: E "+" E

 :: E "*" E

 :: V

 :: N

</pre>

</td>

<td><pre class="rahmenfarbe4">typ E = add(E, E);

mul(E, E);

var(V);

num(N)

</pre>

</td></tr></tbody></table>

<p>Die konkrete Grammatik in diesem Beispiel muss insbesondere die <a href="Operatorrangfolge" title="Operatorrangfolge">Anwendungsreihenfolge von Operatoren</a> auf die (Teil-)Ausdrücke regeln – also dass Punkt- vor Strichrechnung geht und die Teilausdrücke gleicher Priorität von links nach rechts zusammenzufassen sind. Ebenso wird mit Klammerausdrücken die Möglichkeit angeboten, eine andere Zusammenfassung zu bewirken. Dies sind zusammen mit bestimmten Terminalen (hier "(", ")", "+", "*") lediglich Eigenschaften der syntaktischen Oberfläche, die in der späteren Analyse und Weiterverarbeitung keine Rolle mehr spielen. Insbesondere kann auf die Unterscheidung in verschiedene Arten von Ausdrücken (hier E, T und F) sowie die Schlüsselworte völlig verzichtet werden, wie man am abstrakten Syntaxbaum sieht, der auch deutlich näher am "Inhalt" des Ausdrucks ist. Ferner werden konkrete Ableitungsbäume wegen dieser Oberflächendetails nicht nur schnell unübersichtlich, sondern belegen auch als Datenstruktur im Rechner durch ihre Details mehr Speicherplatz als nötig. Dies schlägt sich ebenfalls in der Laufzeit und Kompliziertheit der Programme nieder, die später den Ableitungsbaum weiter verarbeiten sollen. Auch aus technischen Gründen wird die Zergliederung eines Quelltextes daher meist nicht durch einen konkreten Ableitungsbaum dargestellt.

</p>

<div class="mw-heading mw-heading3"><h3 id="Darstellung_abstrakter_Syntaxbäume"><span id="Darstellung_abstrakter_Syntaxb.C3.A4ume"></span>Darstellung abstrakter Syntaxbäume</h3></div>

<p>Neben der im Beispiel gezeigten graphischen Darstellung als (Operator-)Baum werden abstrakte Syntaxbäume technisch auch als <a href="Term#Formale_Definition" title="Term">Terme</a> notiert, z. B.: <code>mul(var('a'), add(var('b'), num(3)))</code>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Abstrakte_Grammatik">Abstrakte Grammatik</h3></div>

<p>Während abstrakte Syntaxbäume <i>Datenstrukturen</i> sind und algebraische Typen bei ihnen in die Rolle der Grammatik treten, wird in der Literatur, speziell im Zusammenhang mit Kalkülen oft nur eine vergröberte, mehrdeutige Grammatik angegeben, die, wie in obigem Beispiel gezeigt, zwar dieselbe Struktur wie die Terme haben, aber noch Schlüsselworte enthalten. Diese Form ermöglicht eine dann vor allem eine angenehme Niederschrift abstrakter Syntaxbäume, die der eigentlichen Quelle oft sehr nahe ist. Meist wird einleitend darauf hingewiesen, dass zur Vereindeutigung Klammern gesetzt werden dürfen. Ein abstrakter Syntaxbaum für das obige Beispiel würde dann tatsächlich als <code>a * (b + 3)</code> niedergeschrieben. Im Kontext dieser Literatur liegt der Blick dabei aber stets auf dem Term. Wie erwähnt, werden die Grenzen zwischen Grammatik und Algebra durch ein Spiel mit der Form verwischt.

</p><p>Ein typisches Beispiel sind die Ausdrücke im <a href="Lambda-Kalk%C3%BCl" title="Lambda-Kalkül">Lambda-Kalkül</a>, deren abstrakte Grammatik oft nur knapp als <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E:=\lambda V.E\,|\,EE\,|\,V}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E:=\lambda V.E\,|\,EE\,|\,V}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b1af65efa3a5e797dbc5a7d08eb470d3f681b5a8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.653ex; height:2.843ex;" alt="{\displaystyle E:=\lambda V.E\,|\,EE\,|\,V}" loading="lazy"></span> niedergeschrieben wird. Dieselbe Technik wird aber auch für umfangreiche Grammatiken eingesetzt.

</p>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li><a href="Ingo_Wegener" title="Ingo Wegener">Ingo Wegener</a>: <cite style="font-style:italic">Theoretische Informatik</cite>. Eine algorithmenorientierte Einführung. B.G. Teubner, Stuttgart, ISBN 3-519-02123-4, 6.1 Beispiele kontextfreier Sprachen und Syntaxbäume, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>147–148</span>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abookitem&rfr_id=info:sid/de.wikipedia.org:Syntaxbaum&rft.atitle=6.1+Beispiele+kontextfreier+Sprachen+und+Syntaxb%C3%A4ume&rft.au=Ingo+Wegener&rft.btitle=Theoretische+Informatik&rft.genre=bookitem&rft.isbn=3519021234&rft.pages=147-148&rft.place=Stuttgart&rft.pub=B.G.+Teubner" style="display:none"> </span></li>

<li><a href="Uwe_Sch%C3%B6ning" title="Uwe Schöning">Uwe Schöning</a>: <cite style="font-style:italic">Theoretische Informatik – kurz gefasst</cite>. 5. Auflage. Spektrum Akademischer Verlag, Heidelberg, ISBN 978-3-8274-1824-1, 1.1.4 Syntaxbäume, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>15–17</span>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abookitem&rfr_id=info:sid/de.wikipedia.org:Syntaxbaum&rft.atitle=1.1.4+Syntaxb%C3%A4ume&rft.au=Uwe+Sch%C3%B6ning&rft.btitle=Theoretische+Informatik+-+kurz+gefasst&rft.edition=5&rft.genre=bookitem&rft.isbn=9783827418241&rft.pages=15-17&rft.place=Heidelberg&rft.pub=Spektrum+Akademischer+Verlag" style="display:none"> </span></li>

<li><a href="Juraj_Hromkovi%C4%8D" title="Juraj Hromkovič">Juraj Hromkovič</a>: <cite style="font-style:italic">Theoretische Informatik</cite>. Formale Sprachen, Berechenbarkeit, Komplexitätstheorie, Algorithmik, Kommunikation und Kryptographie. 3. Auflage. B.G. Teubner Verlag, Heidelberg, ISBN 978-3-8351-0043-5, 10.4 Kontextfreie Grammatiken und Kellerautomaten, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>378</span>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abookitem&rfr_id=info:sid/de.wikipedia.org:Syntaxbaum&rft.atitle=10.4+Kontextfreie+Grammatiken+und+Kellerautomaten&rft.au=Juraj+Hromkovi%C4%8D&rft.btitle=Theoretische+Informatik&rft.edition=3&rft.genre=bookitem&rft.isbn=9783835100435&rft.pages=378&rft.place=Heidelberg&rft.pub=B.G.+Teubner+Verlag" style="display:none"> </span></li>

<li>Hans Zima: <cite style="font-style:italic">Compilerbau I</cite>. Analyse. Bibliographisches Institut, Mannheim/Wien/Zürich 1982, ISBN 3-411-01644-2, 4.3 Abstrakte Bäume und ihre Attributierung, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>216–229</span>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abookitem&rfr_id=info:sid/de.wikipedia.org:Syntaxbaum&rft.atitle=4.3+Abstrakte+B%C3%A4ume+und+ihre+Attributierung&rft.au=Hans+Zima&rft.btitle=Compilerbau+I&rft.date=1982&rft.genre=bookitem&rft.isbn=3411016442&rft.pages=216-229&rft.place=Mannheim%2FWien%2FZ%C3%BCrich&rft.pub=Bibliographisches+Institut" style="display:none"> </span></li>

<li>Stefan Müller: <cite style="font-style:italic">Grammatical Theory. From transformational grammar to constraint-based approaches.</cite> 2. Auflage. Language Science Press, Berlin 2018, ISBN 978-3-96110-074-3, <span style="white-space:nowrap">Kap.<span style="display:inline-block;width:.2em"> </span>2</span> (<a rel="nofollow" class="external text" href="https://langsci-press.org/catalog/book/195">langsci-press.org</a>).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abookitem&rfr_id=info:sid/de.wikipedia.org:Syntaxbaum&rft.atitle=2&rft.au=Stefan+M%C3%BCller&rft.btitle=Grammatical+Theory.+From+transformational+grammar+to+constraint-based+approaches.&rft.date=2018&rft.edition=2&rft.genre=bookitem&rft.isbn=9783961100743&rft.place=Berlin&rft.pub=Language+Science+Press" style="display:none"> </span></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<div class="sisterproject" style="margin:0.1em 0 0 0;"><div class="noresize noviewer" style="display:inline-block; line-height:10px; min-width:1.6em; text-align:center;" aria-hidden="true" role="presentation"><span class="mw-default-size" typeof="mw:File"><span title="Commons"></span></span></div><b><span class=""><a class="external text" href="https://commons.wikimedia.org/wiki/Category:Syntax_trees?uselang=de"><span lang="en">Commons</span>: Syntaxbaum</a></span></b> – Sammlung von Bildern, Videos und Audiodateien</div>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><span class="mw-cite-backlink"><a href="#cite_ref-1">↑</a></span> <span class="reference-text"> Müller (2018), S. 59f.</span>

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2024-09-01" href="https://de.wikipedia.org/wiki/?title=Syntaxbaum&oldid=248228252">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>